# -*- coding: utf-8 -*-

''' Author: Susana Messias nº 6046 '''


from Stack import Stack
from math import sqrt
import sys

# Classe responsável pela criação de uma k-d tree
class KDTree:
	def __init__(self, point_list, N ):
		self.N = N
		self.clean()

		if point_list:
			self.root = self.createNod(point_list, 0)
		pass


	#Limpa a árvore.
	def clean(self):
		self.apontadores_memoria = Stack(self.N)
		for k in xrange(self.N):
			self.apontadores_memoria.push(k)
		self.coordinate =  [[] for k in xrange(self.N)]
		self.parent = [-1 for k in xrange(self.N)]
		self.childLeft = [-1 for k in xrange(self.N)]
		self.childRight = [-1 for k in xrange (self.N)]
		self.root = -1
		pass

	#Remove um determinado ponto da árvore
	def remove(self, coordinate):
		pointRemoved = self.search(coordinate)
		if pointRemoved != -1:
			point_list = []
			for i in xrange(0, self.N):
				if self.coordinate[i] != [] and self.coordinate[i] != coordinate:
					point_list.append(self.coordinate[i])
					pass
				
				pass

			# Cria a árvore novamente
			self.clean()
			if point_list:
				self.root = self.createNod(point_list, 0)
			pass


	#Calcula a distância do vizinho mais próximo, armazenando na stack o ponto por comparar
	def nearestNeighbor(self, coordinate):

		#Adiciona à stack todos os nós no caminho desde o nó dado até ao nó folha mais proximo do ponto 
		def searchLeaf (tree, coordinate, nod, axis, stack):
			index = nod
			
			length = len (coordinate)
			axis = axis % length
			
			while index != -1 and tree.coordinate[index] != coordinate:
				if tree.compare(axis, coordinate, index):
					index = tree.childRight[index]
				else:
					index = tree.childLeft[index]

				if index != -1:
					stack.push((index,axis))

				axis = (axis + 1) % length
				
				pass
			pass

		distance = sys.maxint
		stack = Stack(self.N)

		nod = self.root
		axis = 0

		searchLeaf(self, coordinate, nod, axis, stack)

		lastNod = -1

		#Remover da stack 
		while not stack.stack_empty():
			nodAxis = stack.pop()
			
			distanceTemp = self.distance(coordinate, nodAxis[0]) 

			# Tratamento da distância entre o ponto dado e o nó actual.
			if distanceTemp < distance:
				distance = distanceTemp
				nod = nodAxis[0]
				pass

			#Distância ao eixo
			axisDistance = abs(coordinate[nodAxis[1]] - self.coordinate[nodAxis[0]][nodAxis[1]])

			if axisDistance < distance:
				if lastNod == self.childRight[nodAxis[0]]:
					searchLeaf(self, coordinate, self.childLeft[nodAxis[0]], nodAxis[1] + 1, stack)
				else:
					searchLeaf(self, coordinate, self.childRight[nodAxis[0]], nodAxis[1] + 1, stack)
					pass
				pass


			lastNod = nodAxis[0]
			pass

		return nod


		


	#Cálculo da distância através do teorema de pitágoras 
	def distance(self, coordinate, x):
		distance = 0
		length = len (coordinate)
		for i in xrange(0 ,length):
			temp = self.coordinate[x][i]-coordinate[i] #eixo
			distance += temp * temp
			pass
		distance = sqrt(distance)
		return distance


	# Adiciona pontos à arvore 
	def add(self, coordinate):
		if not self.apontadores_memoria.stack_full():
			point_list = []
			for i in xrange(0, self.N):
				if self.coordinate[i] != []:
					point_list.append(self.coordinate[i])
					pass
				
				pass

			point_list.append(coordinate)
			self.clean()
			if point_list:
				self.root = self.createNod(point_list, 0)
			pass
			
	
	# Gera a árvore
	#in http://en.wikipedia.org/wiki/K-d_tree
	def createNod(self, point_list, depth):
			
		if not point_list:
			return -1

		# Select axis based on depth so that axis cycles through all valid values
		k = len(point_list[0]) # assumes all points have the same dimension
		axis = depth % k


		# Sort point list and choose median as pivot element
		point_list.sort(key = lambda point: point[axis])
		median = len(point_list) / 2 # choose median

		index = self.malloc(point_list[median])

		# Cria o nó e constroi as sub-arvores
		self.childLeft[index] = self.createNod(point_list[:median], depth + 1)
		self.childRight[index] = self.createNod(point_list[median + 1:], depth + 1)

		return index

	#Aloca espaço na "memória" para um nó
	def malloc(self, k):
		x = self.apontadores_memoria.pop()
		self.coordinate[x] = k
		self.parent[x] = -1
		self.childLeft[x] = -1
		self.childRight[x] = -1
		return x


	#Realiza a comparação entre pontos
	def compare(self, axis, coordinate, nod):
		length = len (coordinate) # quantidade de eixos da coordenada

		for i in xrange(axis, length + axis):
			index = i % length
			if coordinate[index] > self.coordinate[nod][index]:
				return True
			elif coordinate[index] < self.coordinate[nod][index]:
				return False

				pass
			pass

		return False

	#Realiza a pesquisa de um determinado ponto
	def search (self, coordinate):
		index = self.root
		axis = 0

		length = len (coordinate)

		while index != -1 and self.coordinate[index] != coordinate:
			if self.compare(axis, coordinate, index):
				index = self.childRight[index]
			else:
				index = self.childLeft[index]

			axis = (axis + 1) % length


		return index


	#Cria uma string que representa a subárvore do nó dado
	def makeString (self, index):
		s = '['

		if self.childLeft[index] == -1:
			s += 'None'
		else:
			s += self.makeString(self.childLeft[index])

		s +=  ', '

		if index == self.root:
			s+= 'root: '
		
		s += str(self.coordinate[index]) + ', '

		if self.childRight[index] == -1:
			s += 'None'
		else:
			s+=self.makeString(self.childRight[index])

		s+=']'

		return s

	#Devolve uma representação da árvore sob a forma de string
	def __str__ (self):
		return self.makeString(self.root)

